#include "Common.hpp"

// Single-level array
// BITS为非类型模板参数 表示需要存多少个的基数树 -以2为底，bits位数的个数
// 注意，一层模型只适用于32位
template <int BITS>
class TCMalloc_PageMap1 {
private:
	static const int LENGTH = 1 << BITS;  // 算出总长度，32位下为2^19个 （2^32byte / 2^13byte = 2^19个）
	void** _array;

public:
	typedef uintptr_t Number;

	//explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) {
	explicit TCMalloc_PageMap1() {
		//array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
		size_t size = sizeof(void*) << BITS;  // 算出存2^bites 个地址所需要的byte
		size_t alignSize = QiHai::SizeClass::_RoundUp(size, 1 << QiHai::SHIFT_PAGE);  // 算出对齐数进行申请
		_array = (void**)QiHai::SystemAlloc(alignSize >> QiHai::SHIFT_PAGE);  // 计算出大概申请多少页
		memset(_array, 0, sizeof(void*) << BITS);  // 初始化为0
	}

	// Return the current value for KEY.  Returns NULL if not yet set,
	// or if k is out of range.
	void* get(Number k) const {
		if ((k >> BITS) > 0) {
			return nullptr;
		}
		return _array[k];
	}

	// REQUIRES "k" is in range "[0,2^BITS-1]".
	// REQUIRES "k" has been ensured before.
	//
	// Sets the value 'v' for key 'k'.
	void set(Number k, void* v) {
		_array[k] = v;
	}
};

// 基数树优化的作用：
// 由于使用STL的哈希的话，需要频繁的加锁（在实际调用中发现锁消耗的性能最大），这样在进行查找页号对应的span的时候，每一块是独立起来的。并且当一个线程申请到
// 一块内存，此页号就固定了，没还回去之前，都一直属于当前执行流，所以以此可以优化性能
// 上面只是一层基数树，对于32位可以使用2层基数树，但是如果是64位程序的话，就需要3层基数树了，扩展内容。
